import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class dataex {

    public static void main(String[] args) {
        //先定义一个中缀的字符串
        String expression = "1+((2/3)*4)-5";
        //把字符串 转换成Arraylist 也就是[1,+,(,(,2,+,3,),*,4,),-,5]
        List<String> infixlist = tofixlist(expression);
        System.out.println("中缀表达式对应的list" +infixlist);
        List<String> paruffix = toparuffix(infixlist);
        System.out.println("后缀表达式对应的list"+paruffix);

    }
    private static int getvalue(String itme) {

        switch (itme){
            case "+":return 1;
            case "-":return 1;
            case "*":return 2;
            case "/":return 2;
            default:
                throw new RuntimeException("未存在该运算符");
        }
    }
    private static List<String> toparuffix(List<String> ls) {
        Stack<String> s1 = new Stack<String>();
        List<String> s2 = new ArrayList<String>();
        for (String itme:ls) {
            if (itme.matches("\\d+")){
                s2.add(itme);
            } else if (itme.equals("(")) {
                s1.push(itme);
            } else if (itme.equals(")")) {
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();
            }else {
                while (s1.size() != 0 && getvalue(s1.peek())>=getvalue(itme)){
                    s2.add(s1.pop());
                }
                s1.push(itme);
            }
         }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }
    private static List<String> tofixlist(String s){
        List<String> ls = new ArrayList<String>();
        int i = 0;
        String str;
        char c;
        do {
            if ((c=s.charAt(i)) < 48|| (c=s.charAt(i)) >57){
                ls.add(""+c);
                i++;
            }else {
                str = "";
                while (i < s.length()&&(c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <=57){
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        }while (i<s.length());
        return ls;
    }

    private static int calculate(List<String> ls){
        Stack<String> stack = new Stack<String>();
        for (String item:ls){
            if (item.matches("\\d+")){
                stack.push(item);
            }else {
                int num2 =Integer.parseInt(stack.pop());
                int num1 =Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")){
                    res = num1+num2;
                } else if (item.equals("-")) {
                    res = num1-num2;
                } else if (item.equals("*")) {
                    res = num1*num2;
                } else if (item.equals("/")) {
                    res =num1/num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(""+res);
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
